package EveryDay;
/**
 * P134 加油站
 * */
public class P134 {
    public static void main(String[] args) {
//        P134Test01 p134Test01=new P134Test01();
//        int[] a={1,2,3,4,5};
//        int[] b={3,4,5,1,2};
//        System.out.println(p134Test01.canCompleteCircuit(a,b));

        P134Test02 p134Test02=new P134Test02();
        int[] a={1,2,3,4,5};
        int[] b={3,4,5,1,2};
        System.out.println(p134Test02.canCompleteCircuit(a,b));
    }
}

/**
 * 解法:模拟，复杂度O(n^2)
 * */
class P134Test01{
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int length=gas.length;

        if(length==1)
            return gas[0]-cost[0]>=0?0:-1;

        int ans=-1;
        for(int i=0;i<length;i++){
            //初始化
            int sum=0;
            sum+=gas[i];
            int num=0;
            int j=i;
            while(num<length-1){
                sum=sum-cost[j];
                if(sum<0) {
                    break;
                }
                j++;
                if(j>length-1){
                    j%=length;
                }
                sum=sum+gas[j];
                num++;
            }
            if(sum>=cost[(j+length)%length]) {
                ans=i;
                break;
            }

        }

        return ans;
    }
}
/**
 * 解法二：贪心,找到局部最优解即可
 * 在本题中，如果从0开始找，x-y区间内到达不了y+1,那么一直都到达不了，需要从y+1开始
 */
class P134Test02{
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int length=gas.length;

        if(length==1)
            return gas[0]-cost[0]>=0?0:-1;

        int i=0;
        while(i<length){

            int num=0;
            int gasNum=0,costNum=0;
            int j=i;
            while (num<length){
                gasNum+=gas[j];
                costNum+=cost[j];
                j=(j+1)%length;

                if(costNum>gasNum)
                    break;
                num++;
            }
            if(num==length){
                return i;
            }
            else{
                i=i+num+1;
            }
        }

        return -1;
    }
}